package dynamicProgramming.baseKnowledge;

/**
 * @author zxc
 * @date 2023/01/18 10:11
 **/

import java.util.Map;

/**
 * 题目 ：爬楼梯的最少成本
 * 题目详述 ：
 * 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值cost[i]（下标从 0 开始）。
 * 每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
 * 请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
 *
 * 提示：
 * 2 <= cost.length <= 1000
 * 0 <= cost[i] <= 999
 */
public class MinCostClimbingStairs_recursion {
    /**
     * 思路 ：
     * 假设 f(i)所代表的是从楼梯第i级台阶继续向上爬所需要的最少成本（即，爬到楼梯的第i级台阶所需要的最少成本 + 第i级台阶所需要的成本）
     * 状态转移方程 ：f(i) = min(f(i - 1) , f(i - 2)) + cost[i];
     *
     * 需要注意的是，状态转移方程有一个隐性条件 ：i >= 2;
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        // 即，爬到楼梯顶端（length）的最少成本需要比较 从楼梯第（length - 1）级向上爬/从楼梯第（length - 2）级向上爬 所需要花费的最少成本来决定
        return Math.min(recursion(cost , length - 1) , recursion(cost , length - 2));
    }
    // recursion方法 ：即代表了从第index级台阶继续向上爬所需要花费的最少成本;
    // （即，爬到楼梯的第i级台阶所需要的最少成本 + 第i级台阶所需要的成本）;
    private int recursion(int[] cost, int index) {
        // 状态转移方程的隐性条件 ：i <= 2;
        if(index < 2){
            // 当index < 2时，则代表了从第index（1/2）级台阶继续向上爬的最少成本 为cost[1]/cost[2];
            return cost[index];
        }
        return Math.min(recursion(cost , index - 1) , recursion(cost , index - 2)) + cost[index];
    }
    /**
     * 问题 ：
     * 虽然代码看起来很简介，但是时间效率极差无比;
     * 为啥呢？
     * （1）主要是因为出现大量的重复计算，极大程度上降低该算法的时间效率;
     * （2）在于求解f(i - 1) 和 f(i - 2)子问题时，会出现重叠部分;
     */
}
